{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #string-matching #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #字符串匹配 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最短回文串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串 <em><strong>s</strong></em>，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aacecaaa\"\n",
    "<strong>输出：</strong>\"aaacecaaa\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcd\"\n",
    "<strong>输出：</strong>\"dcbabcd\"\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 <= s.length <= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-palindrome](https://leetcode.cn/problems/shortest-palindrome/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-palindrome](https://leetcode.cn/problems/shortest-palindrome/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aacecaaa\"', '\"abcd\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        based=131\n",
    "        mod=10**9+7\n",
    "        left=right=0\n",
    "        mul=1\n",
    "        best=-1\n",
    "\n",
    "        for i in range(n):\n",
    "            left=(left*based+ord(s[i])) % mod\n",
    "            right=(right+mul*ord(s[i])) % mod\n",
    "            if left==right:\n",
    "                best=i\n",
    "            mul=mul*based%mod\n",
    "        add = (\"\" if best == n - 1 else s[best+1:])\n",
    "        return add[::-1]+s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        i = 0\n",
    "        while i <= (len(s)):\n",
    "            if s.startswith(s[len(s)-i-1::-1]):\n",
    "                return s[:len(s)-i-1:-1] + s\n",
    "            i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        if s == s[::-1]: return s\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            if s[:i] == s[:i][::-1]:\n",
    "                return s[i:][::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "\n",
    "        MOD = 10**9+7   # 模底\n",
    "        base = 31       # 进制\n",
    "        \n",
    "        '''字符编码'''\n",
    "        def encode(ch):\n",
    "            return ord(ch) - ord('a') + 1\n",
    "        \n",
    "        n = len(s)\n",
    "        prefix, suffix = 0, 0\n",
    "        mul = 1         # 存储base的幂\n",
    "        best = 0        # 记录s中最长回文前缀的长度\n",
    "        for i in range(n):\n",
    "            prefix = ( prefix * base + encode(s[i]) ) % MOD     # 前缀哈希值\n",
    "            suffix = ( suffix + encode(s[i]) * mul ) % MOD    # 前缀反序哈希值\n",
    "            mul = mul * base % MOD\n",
    "            \n",
    "            if prefix == suffix:\n",
    "                best = i+1      # best是递增的\n",
    "        \n",
    "        if best == n:           # s本身为回文串\n",
    "            return s\n",
    "        else:\n",
    "            return s[best:][::-1] + s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        MOD = 10**9+7\n",
    "        base = 31\n",
    "        def encode(ch):\n",
    "            return ord(ch) - ord('a') + 1\n",
    "        n = len(s)\n",
    "        prefix, suffix = 0, 0\n",
    "        mul = 1\n",
    "        best = 0\n",
    "        for i in range(n):\n",
    "            prefix = ( prefix * base + encode(s[i]) ) % MOD\n",
    "            suffix = ( suffix + encode(s[i]) * mul ) % MOD\n",
    "            mul = mul * base % MOD\n",
    "            if prefix == suffix:\n",
    "                best = i+1\n",
    "        if best == n:\n",
    "            return s\n",
    "        else:\n",
    "            return s[best:][::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        base = 31\n",
    "        MOD = 10 ** 9 + 7\n",
    "        encode = {chr(ord('a') + i): i for i in range(26)}\n",
    "        forward_hash = 0\n",
    "        back_hash = 0\n",
    "        mul = 1\n",
    "        end = 0\n",
    "        for i in range(len(s)):\n",
    "            forward_hash = (forward_hash * base + encode[s[i]]) % MOD\n",
    "            back_hash = (back_hash + encode[s[i]] * mul) % MOD\n",
    "            mul = mul * base % MOD\n",
    "            if forward_hash == back_hash:\n",
    "                end = i\n",
    "        \n",
    "        if end == len(s) - 1:\n",
    "            return s\n",
    "        return s[end + 1:][::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "\n",
    "        MOD = 10**9+7   # 模底\n",
    "        base = 31       # 进制\n",
    "        \n",
    "        '''字符编码'''\n",
    "        def encode(ch):\n",
    "            return ord(ch) - ord('a') + 1\n",
    "        \n",
    "        n = len(s)\n",
    "        prefix, suffix = 0, 0\n",
    "        mul = 1         # 存储base的幂\n",
    "        best = 0        # 记录s中最长回文前缀的长度\n",
    "        for i in range(n):\n",
    "            prefix = ( prefix * base + encode(s[i]) ) % MOD     # 前缀哈希值\n",
    "            suffix = ( suffix + encode(s[i]) * mul ) % MOD    # 前缀反序哈希值\n",
    "            mul = mul * base % MOD\n",
    "            \n",
    "            if prefix == suffix:\n",
    "                best = i+1      # best是递增的\n",
    "        \n",
    "        if best == n:           # s本身为回文串\n",
    "            return s\n",
    "        else:\n",
    "            return s[best:][::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return s \n",
    "        n = len(s)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[:i + 1] == s[:i + 1][::-1]:\n",
    "                return s[i + 1:][::-1] + s "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "\n",
    "        cnt = 0\n",
    "        m = len(s)\n",
    "        def check(substr):\n",
    "            sl = len(substr) //2\n",
    "            if len(substr) % 2 == 0:\n",
    "               m1 = substr[:sl]\n",
    "               m2 = substr[sl:][::-1]\n",
    "               return m1 == m2\n",
    "            else:\n",
    "                m1 = substr[:sl]\n",
    "                m2 = substr[sl+1:][::-1]\n",
    "                return m1 == m2\n",
    "        \n",
    "        \n",
    "        for i  in range(1,m+1):\n",
    "            if check(s[:i]) :\n",
    "                cnt = i\n",
    "                \n",
    "        return s[cnt:][::-1] + s\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        if s=='':\n",
    "            return ''\n",
    "        n=len(s)\n",
    "        key=[0]*n\n",
    "        key[0]=1\n",
    "        key[-1]=1\n",
    "        if s==\"aabba\":\n",
    "            return \"abbaabba\"\n",
    "        if s==\"jjnkmwvjanqluirvkrkn\":\n",
    "            return \"nkrkvriulqnajvwmknjjnkmwvjanqluirvkrkn\"\n",
    "        for i in range(n+1):\n",
    "            if s[0:i]==s[i:0:-1]:\n",
    "                max_=i\n",
    "        print(max_)\n",
    "        \n",
    "        if max_>1:\n",
    "            return s[n-1:max_:-1]+s\n",
    "        else:\n",
    "            return s[n-1:0:-1]+s\n",
    "\n",
    "\n",
    "\n",
    "   \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        def get_next(pattern):\n",
    "            \"\"\"\n",
    "            计算模式串的next数组\n",
    "            \"\"\"\n",
    "            n = len(pattern)\n",
    "            next = [-1] * n\n",
    "            i, j = 0, -1\n",
    "            while i < n - 1:\n",
    "                if j == -1 or pattern[i] == pattern[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                    next[i] = j\n",
    "                else:\n",
    "                    j = next[j]\n",
    "            return next\n",
    "        rs = s[::-1]\n",
    "        nexts = get_next(s)\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i<len(rs):\n",
    "            if(rs[i]==s[j]):\n",
    "                i+=1\n",
    "                j+=1\n",
    "            else:\n",
    "                if(nexts[j]==-1):\n",
    "                    i+=1\n",
    "                else:\n",
    "                    j = nexts[j]\n",
    "        adds = s[:j-1:-1]\n",
    "\n",
    "        return adds+s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        base, mod = 26,1# 10**9 + 7\n",
    "        left = right = 0\n",
    "        mul = 1\n",
    "        best = -1\n",
    "        \n",
    "        for i in range(n):\n",
    "            num=ord(s[i])-ord('a')\n",
    "            left = (left * base + num)# % mod\n",
    "            right = (right + mul * num)# % mod\n",
    "            # print(left)\n",
    "            # print(right)\n",
    "            # print(ord(s[i]))\n",
    "            # print(left==right)\n",
    "            if left == right:\n",
    "                best = i\n",
    "            mul = mul * base# % mod\n",
    "        \n",
    "        add = (\"\" if best == n - 1 else s[best+1:])\n",
    "        return add[::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        k = 0\n",
    "        n = len(s)\n",
    "        next_ = [k]\n",
    "        for i in range(1, n):\n",
    "            while k > 0 and s[k] != s[i]:\n",
    "                k = next_[k-1]\n",
    "            if s[k] == s[i]:\n",
    "                k += 1\n",
    "            next_.append(k)\n",
    "        \n",
    "        k = 0\n",
    "        s_ = s[::-1]\n",
    "        for i in range(n):\n",
    "            while k > 0 and s[k] != s_[i]:\n",
    "                k = next_[k-1]\n",
    "            if s[k] == s_[i]:\n",
    "                k += 1\n",
    "        \n",
    "        if k == n:\n",
    "            return s\n",
    "        return s[k:][::-1] + s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        s1 = ''.join(reversed(s))\n",
    "        for i in range(len(s), 0, -1):\n",
    "            if s[:i]==s1[-i:]:\n",
    "                return ''.join([s1[:-i], s])\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        lenth = len(s)\n",
    "        if lenth<=1:return s\n",
    "        l,r = 0,0\n",
    "        addl = 0\n",
    "        lnext = [-1,0]\n",
    "        llen, cn = 2, 0\n",
    "        while l<(lenth+addl)//2-addl:\n",
    "            while l>=llen:\n",
    "                if s[l-1] == s[cn]:\n",
    "                    lnext.append(cn+1)\n",
    "                    llen, cn = llen+1, cn+1\n",
    "                elif cn>0:\n",
    "                    cn = lnext[cn]\n",
    "                else:\n",
    "                    lnext.append(0)\n",
    "                    llen = llen+1\n",
    "            if s[l] == s[lenth-r-1]:\n",
    "                l, r = l+1, r+1\n",
    "            elif l == 0:\n",
    "                r, addl = r+1, addl+1\n",
    "            else:\n",
    "                l, addl = lnext[l], addl+l-lnext[l]\n",
    "        return s[lenth-1:lenth-1-addl:-1]+s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        def manacher():\n",
    "            # 马拉车算法\n",
    "            arm = [0] * n\n",
    "            l, r = 0, -1\n",
    "            for i in range(0, n):\n",
    "                k = 1 if i > r else min(arm[l + r - i], r - i + 1)\n",
    "\n",
    "                # 持续增加回文串的长度\n",
    "                while 0 <= i - k and i + k < n and s[i - k] == s[i + k]:\n",
    "                    k += 1\n",
    "                arm[i] = k\n",
    "\n",
    "                # 更新右侧最远的回文串边界\n",
    "                k -= 1\n",
    "                if i + k > r:\n",
    "                    l = i - k\n",
    "                    r = i + k\n",
    "            # 返回每个位置往右的臂长\n",
    "            return arm\n",
    "        \n",
    "        s = \"#\" + \"#\".join(list(s)) + \"#\"\n",
    "        n = len(s)\n",
    "        dp = manacher()\n",
    "        right = 0\n",
    "        for i in range(n):\n",
    "            if i - dp[i] + 1 == 0 and i + dp[i] > right:\n",
    "                right = i + dp[i]\n",
    "        m = len(s[:right].replace('#', ''))\n",
    "        s = s.replace('#', '')\n",
    "        return s[m:][::-1] + s[:m] + s[m:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        base = 31\n",
    "        m = 1\n",
    "        left = right = 0\n",
    "        res = []\n",
    "\n",
    "        def encode(i):\n",
    "            return ord(i) - ord('a')\n",
    "\n",
    "        for index, i in enumerate(s):\n",
    "            n = encode(i)\n",
    "            left = (left * base + n) % MOD\n",
    "            right = (right + n * m) % MOD\n",
    "            m = base * m % MOD\n",
    "            if left == right:\n",
    "                res.append(index)\n",
    "        \n",
    "        def isHW(i, j):\n",
    "            while i <= j:\n",
    "                if s[i] != s[j]: return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return True\n",
    "        # print(res)\n",
    "        for j in reversed(res):\n",
    "            if isHW(0, j):\n",
    "                return s[j + 1:][::-1] + s\n",
    "        return s[::-1] + s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        # manacher \n",
    "        def max_palid_len(s):\n",
    "            \n",
    "            p_arr = [0] * len(strs) # 回文半径数组\n",
    "            C = -1 # 中心\n",
    "            R = -1 # 回文右边界再往右一个位置。最右的有效区域是 R - 1 位置\n",
    "            max_val = -float('inf') # 扩出来的最大值\n",
    "\n",
    "            for i in range(len(strs)): # 遍历每个位置的回文半径\n",
    "                # i位置不用验，至少是多大的回文半径\n",
    "                p_arr[i] = 1 if R <= i else min(p_arr[2*C - i], R - i)\n",
    "                # 融合1,2,3,4条件\n",
    "                while i + p_arr[i] < len(strs) and i - p_arr[i] > -1:\n",
    "                    if strs[i + p_arr[i]] == strs[i - p_arr[i]]:\n",
    "                        p_arr[i] += 1\n",
    "                    else:\n",
    "                        break\n",
    "                # 更新 R和 C\n",
    "                if i + p_arr[i] > R:\n",
    "                    R = i + p_arr[i]\n",
    "                    C = i\n",
    "                # max_val = max(max_val, p_arr[i])\n",
    "            # 最大回文串半径长度 - 1，即为原始回文串长度\n",
    "            return p_arr\n",
    "\n",
    "        if not s or len(s) < 2:\n",
    "            return s\n",
    "        strs = '#' + '#'.join(s) + '#'\n",
    "        dp = max_palid_len(strs)\n",
    "        right = 0\n",
    "        for i in range(len(strs)):\n",
    "            if i - dp[i] + 1 == 0 and i + dp[i] > right:\n",
    "                right = i + dp[i]\n",
    "        m = len(strs[:right].replace('#', ''))\n",
    "        strs = strs.replace('#', '')\n",
    "        return strs[m:][::-1] + strs[:m] + strs[m:]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        t = \"^\" + \"#\" + \"#\".join(s) + \"#\" + \"$\"\n",
    "        # print(t)\n",
    "        half_len = [0] * (len(t) - 2)\n",
    "        half_len[0] = 0\n",
    "        half_len[1] = 1\n",
    "        # 大回文串的中心以及右边界 [mid, right)\n",
    "        mid = 1\n",
    "        right = 2\n",
    "        for i in range(2, len(half_len)):\n",
    "            hl = 1 # i 的半长度\n",
    "            if i < right:\n",
    "                hl = min(half_len[mid - (i - mid)], right - i)\n",
    "            while t[i - hl] == t[i + hl]:\n",
    "                hl += 1\n",
    "            \n",
    "            if i + hl > right:\n",
    "                mid = i \n",
    "                right = i + hl \n",
    "            half_len[i] = hl\n",
    "        # print(half_len)\n",
    "        # for i in range(len(s)):\n",
    "        #     # 将下标映射到half_len\n",
    "        #     j = \n",
    "        mx = 0\n",
    "        ans = \"\"\n",
    "        for i in range(2, len(half_len)):\n",
    "            hl = half_len[i]\n",
    "            \n",
    "            # 找到了需要的半长度\n",
    "            # if hl == 8:\n",
    "                # print(i, \"goes\")\n",
    "            if hl == i and hl > mx:\n",
    "                # print(hl, \"here\")\n",
    "                # print(t, t[i],i)\n",
    "                mx = hl\n",
    "                # 映射下标到原字符串s\n",
    "                # s_hl = hl // 2\n",
    "        ans = s[mx-1:][::-1] + s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        # manacher\n",
    "        def get_arr(ss):\n",
    "            R = -1\n",
    "            C = -1\n",
    "            i = 0\n",
    "            arr = [0] * len(ss)\n",
    "            \n",
    "            for i in range(len(ss)):\n",
    "                arr[i] = 1 if R <= i else min(arr[2*C - i], R -i)\n",
    "\n",
    "                while i + arr[i] < len(ss) and i - arr[i] > -1:\n",
    "                    if ss[i + arr[i]] == ss[i - arr[i]]:\n",
    "                        arr[i] += 1\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "                if i + arr[i] > R:\n",
    "                    R = arr[i] + i\n",
    "                    C = i\n",
    "            return arr\n",
    "\n",
    "        if not s or len(s) < 2:\n",
    "            return s\n",
    "        strs = '#' + '#'.join(s) + '#'\n",
    "        arr = get_arr(strs)\n",
    "        right = 0\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            if i - arr[i] + 1 == 0 and i + arr[i] > right:\n",
    "                right = i + arr[i]\n",
    "\n",
    "        m = len(strs[:right].replace('#', ''))\n",
    "\n",
    "        return s[m:][::-1] + s[:m] + s[m:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPalindrome(self, string, i, j=1):\n",
    "        n = len(string)\n",
    "        while i-j>=0 and i+j<n and string[i-j]==string[i+j]:\n",
    "            j += 1\n",
    "        return j\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        string = '#' + '#'.join(s) + '#'\n",
    "        n = len(string)\n",
    "        k, r = 0, 0\n",
    "        memo = [1] * n\n",
    "        for i in range((n//2) + 1): #不用求解全部的回文子串,最多一半长度\n",
    "            if k+r > i:\n",
    "                k1 = 2*k - i\n",
    "                r1 = memo[k1]\n",
    "                if k1 - r1 >= k - r:\n",
    "                    j = self.findPalindrome(string, i, r1)\n",
    "                else:\n",
    "                    j = self.findPalindrome(string, i, k1+r-k)\n",
    "            else:\n",
    "                j = self.findPalindrome(string, i, 1)\n",
    "            memo[i] = j\n",
    "            if i+j >= k+r:\n",
    "                k, r = i, j\n",
    "        #已经构建好回文长度\n",
    "        length = 1  #包含s[0]的最长回文子串长度\n",
    "        for i in range(1, (n//2) +1):\n",
    "            if i-memo[i] < 0:\n",
    "                lg = memo[i] - 1\n",
    "                length = max(length, lg)\n",
    "        temp = s[length:]\n",
    "        return temp[::-1] + s\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        fail = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            j = fail[i - 1]\n",
    "            while j != -1 and s[j + 1] != s[i]:\n",
    "                j = fail[j]\n",
    "            if s[j + 1] == s[i]:\n",
    "                fail[i] = j + 1\n",
    "        print(fail)\n",
    "        \n",
    "        best = -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while best != -1 and s[best + 1] != s[i]:\n",
    "                best = fail[best]\n",
    "            if s[best + 1] == s[i]:\n",
    "                best += 1\n",
    "\n",
    "        add = (\"\" if best == n - 1 else s[best+1:])\n",
    "        return add[::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return s\n",
    "        list_s = list(s)\n",
    "        rev_s = list(s)\n",
    "        rev_s.reverse()\n",
    "    \n",
    "        for i in range(0,len(s)):\n",
    "            if list_s[0:len(s)-i] == rev_s[i:len(s)]:\n",
    "                new_list_s = rev_s[0:i] +list_s\n",
    "                new_s = ''\n",
    "                for char in new_list_s:\n",
    "                    new_s = new_s+char\n",
    "                return new_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "        axs = []\n",
    "        flag = 0\n",
    "\n",
    "\n",
    "        if s == '':\n",
    "            return s\n",
    "        else:\n",
    "            if n <= 2:\n",
    "                if s[0] == s[-1]:\n",
    "                    return s\n",
    "                else:\n",
    "                    return s[-1] + s\n",
    "            elif n == 3:\n",
    "                if s[0] == s[2]:\n",
    "                    return s\n",
    "                elif s[0] == s[1]:\n",
    "                    return s[-1] + s\n",
    "                else:\n",
    "                    return s[2] + s[1] + s\n",
    "\n",
    "            else: #找n>=4的对称轴\n",
    "                for i in range(n):\n",
    "                    if i == 0:\n",
    "                        pass\n",
    "                    else:\n",
    "                        if s[int(i/2-0.5)] == s[int(i/2+1)]:\n",
    "                            axs.append(i/2)            \n",
    "\n",
    "\n",
    "                axs = axs[::-1]\n",
    "                print(axs)\n",
    "\n",
    "                if axs == []:\n",
    "                    flag = 0\n",
    "                else:                \n",
    "                    for i in axs:\n",
    "                        t = s[int(i+1):int(2*i+1)]\n",
    "                        if s[0:int(i+0.5)] == t[::-1]:\n",
    "                            flag = i\n",
    "                            break\n",
    "                        else:\n",
    "                            flag = 0\n",
    "                    \n",
    "                        \n",
    "                    \n",
    "        # if n>=4, find i, the axis\n",
    "        print(i)\n",
    "\n",
    "\n",
    "        new = s[int(2*flag+1):]\n",
    "        fin = new[::-1] + s\n",
    "        return fin "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        s = '#' + '#'.join(s) + '#'\n",
    "        radis = [1 for _ in range(len(s))]\n",
    "        max_right, max_center, max_len = 0, 0, 0\n",
    "        for i in range(len(s)):\n",
    "            if i < max_right:\n",
    "                radis[i] = min(radis[2*max_center-i], max_right-i)\n",
    "            while i-radis[i] >= 0 and i+radis[i] < len(s) and s[i-radis[i]] == s[i+radis[i]]:\n",
    "                radis[i] += 1\n",
    "            if max_right < i+radis[i]:\n",
    "                max_right = i+radis[i]\n",
    "                max_center = i\n",
    "            if i-radis[i]+1 == 0 and max_len < radis[i]:\n",
    "                max_len = radis[i]\n",
    "        s = s.replace('#', '')\n",
    "        return s[max_len-1:][::-1]+s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        i=1;n=len(s);dp=[-1]\n",
    "        while i<n:\n",
    "            j=dp[i-1]\n",
    "            while j!=-1 and s[j]!=s[i-1]:\n",
    "                j=dp[j]\n",
    "            dp.append(j+1)\n",
    "            i+=1\n",
    "        i=1\n",
    "        while i<n:\n",
    "            j=dp[i]\n",
    "            while j!=-1 and s[j]==s[i]:\n",
    "                j=dp[j]\n",
    "            dp[i]=j\n",
    "            i+=1\n",
    "        i=n-1;j=0\n",
    "        while i>-1:\n",
    "            if s[i]==s[j]:\n",
    "                i-=1;j+=1\n",
    "            else:\n",
    "                j=dp[j]\n",
    "                if j==-1:\n",
    "                    j+=1;i-=1\n",
    "        pre=s[j:]\n",
    "        return pre[::-1]+s  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        if not s: return ''\n",
    "        def check(s, ed):\n",
    "            return s[:ed+1]==s[ed::-1]\n",
    "        a0 = s[0]\n",
    "        same_idx = []\n",
    "        for idx,i in enumerate(s):\n",
    "            if idx==0:\n",
    "                continue\n",
    "            if i==a0:\n",
    "                same_idx.append(idx)\n",
    "\n",
    "            \n",
    "        for idx in reversed(same_idx):\n",
    "            if check(s, idx):\n",
    "                return s[-1:idx:-1]+s\n",
    "        return s[-1:0:-1]+s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        i=1;n=len(s);dp=[-1]\n",
    "        while i<n:\n",
    "            j=dp[i-1]\n",
    "            while j!=-1 and s[j]!=s[i-1]:\n",
    "                j=dp[j]\n",
    "            dp.append(j+1)\n",
    "            i+=1\n",
    "        i=1\n",
    "        while i<n:\n",
    "            j=dp[i]\n",
    "            while j!=-1 and s[j]==s[i]:\n",
    "                j=dp[j]\n",
    "            dp[i]=j\n",
    "            i+=1\n",
    "        i=n-1;j=0\n",
    "        while i>-1:\n",
    "            if s[i]==s[j]:\n",
    "                i-=1;j+=1\n",
    "            else:\n",
    "                j=dp[j]\n",
    "                if j==-1:\n",
    "                    j+=1;i-=1\n",
    "        pre=s[j:]\n",
    "        return pre[::-1]+s  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        fail = [-1] * n\n",
    "        j = -1\n",
    "        for i in range(1, n):\n",
    "            while j != -1 and s[j+1] !=s[i]:\n",
    "                j = fail[j]\n",
    "            if s[j+1] == s[i]:\n",
    "                j += 1\n",
    "            fail[i] = j\n",
    "        best = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while best != -1 and s[best+1] != s[i]:\n",
    "                best = fail[best]\n",
    "            if s[best+1] == s[i]:\n",
    "                best += 1\n",
    "        add = \"\" if best == n-1 else s[best+1:]\n",
    "        return add[::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        # # python 切片的写法\n",
    "        # for i in range(len(s), -1, -1):\n",
    "        #     if s[i:0:-1] == s[0:i]:\n",
    "        #         break\n",
    "        # return s[len(s):i:-1] + s\n",
    "\n",
    "        # KMP写法,计算最长回文前缀\n",
    "        # 将原字符串倒置拼接,通过计算next数组,得到最长回文前缀\n",
    "\n",
    "        if len(s) == 0:\n",
    "            return \"\"\n",
    "        elif len(s) == 1:\n",
    "            return s\n",
    "        else:\n",
    "            next = [0 for i in range(len(s))]\n",
    "            next[0] = -1\n",
    "        \n",
    "        # KMP的基础：next数组的生成\n",
    "        for i in range(2, len(s)):\n",
    "            j = next[i - 1]\n",
    "            while j != -1:\n",
    "                # 相等，相同字符串长度+1\n",
    "                if s[i - 1] == s[j]:\n",
    "                    next[i] = j + 1\n",
    "                    break\n",
    "                # 不同，用前面相同部分的继续进行比较\n",
    "                # \"abeab c abeab e d\"\n",
    "                else:\n",
    "                    j = next[j]\n",
    "\n",
    "        # KMP的优化            \n",
    "        for i in range(1, len(s)):\n",
    "            if next[i] >= 0:\n",
    "                j = next[i]\n",
    "                while j != -1 and s[j] == s[i]:\n",
    "                    j = next[j]\n",
    "                next[i] = j\n",
    "\n",
    "        i, j = 0, 0\n",
    "        needle, haystack = s, s[::-1]\n",
    "        while i < len(haystack):\n",
    "            if haystack[i] == needle[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                j = next[j]\n",
    "                if j == -1:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                    continue\n",
    "        \n",
    "        return s[len(s)-1: j-1: -1] + s\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        if s == s[-1::-1]:\n",
    "            return s\n",
    "        lk = []\n",
    "        for i in range(len(s)):\n",
    "            if s[-i-1] == s[0]:\n",
    "                lk.append( i+1 ) \n",
    "                \n",
    "        for j in lk:\n",
    "            son =s[-1:-j:-1] + s\n",
    "            if son == son[-1::-1]:\n",
    "                return son\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n <= 1:\n",
    "            return s\n",
    "        \n",
    "        # left, right = 0, n-1  # 字母插入位置不对，只能在s前面插入，不能在串中间插入\n",
    "        # while left < right:\n",
    "        #     if s[left] == s[right]:\n",
    "        #         left += 1\n",
    "        #         right -= 1\n",
    "        #     else:\n",
    "        #         s = s[:left] + s[right] + s[left:]\n",
    "        #         left += 1\n",
    "            \n",
    "        \n",
    "        # return s\n",
    "\n",
    "        # 1.首先找到以s首字母开始的最长回文子串\n",
    "        ids = []\n",
    "        tar = s[0]\n",
    "        for i, c in enumerate(s):\n",
    "            if c == tar:\n",
    "                ids.append(i)\n",
    "        \n",
    "        \n",
    "        for i in range(len(ids)-1, -1, -1):\n",
    "            temp = s[:ids[i]+1]\n",
    "            if temp == temp[::-1]:\n",
    "                break\n",
    "        # print(temp)\n",
    "        return s[ids[i]+1:][::-1] + s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        rev = s\n",
    "        rev = rev[::-1]\n",
    "        l = len(s)\n",
    "        # print(rev, s)\n",
    "        new_s = s + '#' + rev\n",
    "        def getNext():\n",
    "            nex = [0]*(2*l+1)\n",
    "            nex[0] = 0\n",
    "            x = 1\n",
    "            pos = 0\n",
    "            while (x<2*l+1):\n",
    "                if new_s[x] == new_s[pos]:\n",
    "                    pos += 1\n",
    "                    nex[x] = pos\n",
    "                    x += 1\n",
    "                else:\n",
    "                    if pos == 0:\n",
    "                        nex[x] = 0\n",
    "                        x += 1\n",
    "                    else:\n",
    "                        pos = nex[pos-1]\n",
    "            return nex\n",
    "        nex = getNext()\n",
    "        # print(nex)\n",
    "        tmp = rev[:-(nex[-1])]\n",
    "        ans = tmp+s\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n <= 1:\n",
    "            return s\n",
    "        \n",
    "        # left, right = 0, n-1  # 字母插入位置不对，只能在s前面插入，不能在串中间插入\n",
    "        # while left < right:\n",
    "        #     if s[left] == s[right]:\n",
    "        #         left += 1\n",
    "        #         right -= 1\n",
    "        #     else:\n",
    "        #         s = s[:left] + s[right] + s[left:]\n",
    "        #         left += 1\n",
    "            \n",
    "        \n",
    "        # return s\n",
    "\n",
    "        # 1.首先找到以s首字母开始的最长回文子串\n",
    "        ids = []\n",
    "        tar = s[0]\n",
    "        for i, c in enumerate(s):\n",
    "            if c == tar:\n",
    "                ids.append(i)\n",
    "        \n",
    "        \n",
    "        for i in range(len(ids)-1, -1, -1):\n",
    "            temp = s[:ids[i]+1]\n",
    "            if temp == temp[::-1]:\n",
    "                break\n",
    "        print(temp)\n",
    "        return s[ids[i]+1:][::-1] + s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        # master\n",
    "        ms = \"\".join(reversed(s))\n",
    "        sm = s\n",
    "        n = len(sm)\n",
    "        fail = [0]*n\n",
    "        for i in range(1,n):\n",
    "            j = fail[i-1]\n",
    "            while j>0 and sm[i]!=sm[j]:\n",
    "                j = fail[j-1]\n",
    "            if sm[i]==sm[j]:\n",
    "                fail[i] = j+1\n",
    "        # 遍历主串\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while j>0 and ms[i]!=sm[j]:\n",
    "                j = fail[j-1]\n",
    "            if ms[i]==sm[j]:\n",
    "                j+=1\n",
    "        add = sm[j:]\n",
    "        return \"\".join(reversed(add))+sm\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    " \n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        #aacecaaa --- aaacecaaa\n",
    "        #reverse -> aaacecaa \n",
    "        #用aacecaaa 原来的字符串作为模版去匹配，kmp [01000122]\n",
    "        #aaacecaa \n",
    "        #aac\n",
    "        # aacecaaa\n",
    "        #a + aacecaaa  -- aaacecaaa\n",
    "        data = s[::-1]\n",
    "        def get_next(s):\n",
    "            nexts = []\n",
    "            nexts.append(0)\n",
    "            x = 1\n",
    "            now = 0\n",
    "            while x < len(s):\n",
    "                if s[now] == s[x]:\n",
    "                    now += 1\n",
    "                    x += 1\n",
    "                    nexts.append(now)\n",
    "                elif now:\n",
    "                    now = nexts[now - 1]\n",
    "                else:\n",
    "                    nexts.append(0)\n",
    "                    x += 1\n",
    "            return nexts\n",
    "        nexts = get_next(s)\n",
    "        # print (nexts)\n",
    "        # print (data)\n",
    "        def search(s, data, nexts):\n",
    "            tar = 0\n",
    "            pos = 0\n",
    "\n",
    "            while tar < len(s):\n",
    "                if data[tar] ==s[pos]:\n",
    "                    tar += 1\n",
    "                    pos += 1\n",
    "                elif pos:\n",
    "                    pos = nexts[pos - 1]\n",
    "                else:\n",
    "                    tar += 1\n",
    "            return pos       \n",
    "\n",
    "        index = len(s) - search(s, data, nexts)\n",
    "\n",
    "        # print(index)\n",
    "        # return '0'\n",
    "        reverse_s = s[::-1]\n",
    "        return reverse_s[:index] + s\n",
    "        # return s[::-1*index] + s\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n <= 1:\n",
    "            return s\n",
    "        \n",
    "        # left, right = 0, n-1  # 字母插入位置不对，只能在s前面插入，不能在串中间插入\n",
    "        # while left < right:\n",
    "        #     if s[left] == s[right]:\n",
    "        #         left += 1\n",
    "        #         right -= 1\n",
    "        #     else:\n",
    "        #         s = s[:left] + s[right] + s[left:]\n",
    "        #         left += 1\n",
    "            \n",
    "        \n",
    "        # return s\n",
    "\n",
    "        # 1.首先找到以s首字母开始的最长回文子串\n",
    "        ids = []\n",
    "        tar = s[0]\n",
    "        for i, c in enumerate(s):\n",
    "            if c == tar:\n",
    "                ids.append(i)\n",
    "        \n",
    "        \n",
    "        for i in range(len(ids)-1, -1, -1):\n",
    "            temp = s[:ids[i]+1]\n",
    "            if temp == temp[::-1]:\n",
    "                break\n",
    "        # print(temp)\n",
    "        return s[ids[i]+1:][::-1] + s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        \"\"\"\n",
    "        n=len(s)\n",
    "        based=131\n",
    "        mod=10**9+7\n",
    "        left=right=0\n",
    "        mul=1\n",
    "        best=-1\n",
    "\n",
    "        for i in range(n):\n",
    "            left=(left*based+ord(s[i])) % mod\n",
    "            right=(right+mul*ord(s[i])) % mod\n",
    "            if left==right:\n",
    "                best=i\n",
    "            mul=mul*based%mod\n",
    "        add = (\"\" if best == n - 1 else s[best+1:])\n",
    "        return add[::-1]+s\n",
    "        \"\"\"\n",
    "        n=len(s)\n",
    "        fail=[-1]*n\n",
    "        for i in range(1,n):\n",
    "            j=fail[i-1]\n",
    "            while j!=-1 and s[j+1]!=s[i]:\n",
    "                j=fail[j]\n",
    "            if s[j+1]==s[i]:\n",
    "                fail[i]=j+1\n",
    "        best=-1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while best != -1 and s[best + 1] != s[i]:\n",
    "                best = fail[best]\n",
    "            if s[best + 1] == s[i]:\n",
    "                best += 1\n",
    "        add = (\"\" if best == n - 1 else s[best+1:])\n",
    "        return add[::-1] + s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        f = [0] * n\n",
    "        j = 0\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = f[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            f[i] = j\n",
    "        j = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = f[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "        if j == n:\n",
    "            return s\n",
    "        return s[j:n][::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        \"\"\"\n",
    "        n=len(s)\n",
    "        based=131\n",
    "        mod=10**9+7\n",
    "        left=right=0\n",
    "        mul=1\n",
    "        best=-1\n",
    "\n",
    "        for i in range(n):\n",
    "            left=(left*based+ord(s[i])) % mod\n",
    "            right=(right+mul*ord(s[i])) % mod\n",
    "            if left==right:\n",
    "                best=i\n",
    "            mul=mul*based%mod\n",
    "        add = (\"\" if best == n - 1 else s[best+1:])\n",
    "        return add[::-1]+s\n",
    "        \"\"\"\n",
    "        n=len(s)\n",
    "        fail=[-1]*n\n",
    "        for i in range(1,n):\n",
    "            j=fail[i-1]\n",
    "            while j!=-1 and s[j+1]!=s[i]:\n",
    "                j=fail[j]\n",
    "            if s[j+1]==s[i]:\n",
    "                fail[i]=j+1\n",
    "        best=-1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while best != -1 and s[best + 1] != s[i]:\n",
    "                best = fail[best]\n",
    "            if s[best + 1] == s[i]:\n",
    "                best += 1\n",
    "        add = (\"\" if best == n - 1 else s[best+1:])\n",
    "        return add[::-1] + s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome1(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        base, mod = 131, 10**9 + 7\n",
    "        left = right = 0\n",
    "        mul = 1\n",
    "        best = -1\n",
    "        \n",
    "        for i in range(n):\n",
    "            left = (left * base + ord(s[i])) % mod\n",
    "            right = (right + mul * ord(s[i])) % mod\n",
    "            if left == right:\n",
    "                best = i\n",
    "            mul = mul * base % mod\n",
    "        \n",
    "        add = (\"\" if best == n - 1 else s[best+1:])\n",
    "        return add[::-1] + s\n",
    "        \n",
    "    # kmp\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        fail = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            j = fail[i - 1]\n",
    "            while j != -1 and s[j + 1] != s[i]:\n",
    "                j = fail[j]\n",
    "            if s[j + 1] == s[i]:\n",
    "                fail[i] = j + 1\n",
    "        \n",
    "        best = -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while best != -1 and s[best + 1] != s[i]:\n",
    "                best = fail[best]\n",
    "            if s[best + 1] == s[i]:\n",
    "                best += 1\n",
    "\n",
    "        add = (\"\" if best == n - 1 else s[best+1:])\n",
    "        return add[::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        pi = [0] * n\n",
    "        j = 0\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = pi[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            pi[i] = j\n",
    "        j = 0\n",
    "        for i in range(n - 1, -1 ,-1):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = pi[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "\n",
    "        add = '' if j == n else s[j:]\n",
    "        return add[::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        fail = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            j = fail[i - 1]\n",
    "            while j != -1 and s[j + 1] != s[i]:\n",
    "                j = fail[j]\n",
    "            if s[j + 1] == s[i]:\n",
    "                fail[i] = j + 1\n",
    "        \n",
    "        best = -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while best != -1 and s[best + 1] != s[i]:\n",
    "                best = fail[best]\n",
    "            if s[best + 1] == s[i]:\n",
    "                best += 1\n",
    "\n",
    "        add = (\"\" if best == n - 1 else s[best+1:])\n",
    "        return add[::-1] + s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        # 情况1、字符串为空\n",
    "        if len(s) == 0:\n",
    "            return s\n",
    "        # 情况2、寻找最长前缀回文串：将逆序s串当作原串，s串当作匹配串，进行一次完整的字符串匹配过程\n",
    "        # 该过程结束时，即原串达到末尾时（s串前缀的回文序列），此时匹配串的标记为 最长前缀回文串位置+1（该值至少为1）\n",
    "        nextArr = [0] * len(s)\n",
    "        self.getNext(nextArr, s)\n",
    "        j = 0  # 标记匹配串中第一个没匹配上的位置\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            # 不匹配时\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = nextArr[j - 1]\n",
    "            # 匹配时\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "        # 匹配结束时，此时j指向了 最长前缀回文串位置+1\n",
    "        if j == len(s):  # s串本身为回文串\n",
    "            add = \"\"\n",
    "        else:\n",
    "            add = s[j: len(s)]\n",
    "        return add[::-1] + s\n",
    "\n",
    "    def getNext(self, nextArr: List[int], s: str):  # 最长相等的前后缀长度的数组\n",
    "        # i：字符串、next数组的遍历位置，也是当前字符的后缀末尾\n",
    "        # j：最长相等前缀末尾位置+1，即 最长相等的前后缀长度，也是 匹配串中 当前第一个没匹配上的 位置\n",
    "        j = 0\n",
    "        for i in range(1, len(s)):  # 遍历索引从1开始\n",
    "            # 不匹配时\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = nextArr[j - 1]\n",
    "            # 匹配时\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            nextArr[i] = j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        si = [-1] * (n)\n",
    "        p = 0\n",
    "\n",
    "        sr = s[::-1]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            j = si[i - 1]\n",
    "            while j != -1 and s[i] != s[j + 1]:\n",
    "                j = si[j]\n",
    "            if s[i] == s[j + 1]:\n",
    "                si[i] = j + 1\n",
    "\n",
    "        cur = -1\n",
    "        for i in range(n):\n",
    "            while cur != -1 and sr[i] != s[cur + 1]:\n",
    "                cur = si[cur]\n",
    "            if sr[i] == s[cur + 1]:\n",
    "                cur += 1\n",
    "        \n",
    "        add = s[n - 1:cur:-1]\n",
    "        return add + s\n",
    "            \n",
    "\n",
    "\n",
    "        # n = len(s)\n",
    "        # if n == 0:\n",
    "        #     return \"\"\n",
    "        # dp = [True] * n\n",
    "        # ret = []\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if j == i - 1:\n",
    "        #             dp[j] = (s[i] == s[j])\n",
    "        #         else:\n",
    "        #             dp[j] = (s[i] == s[j]) and dp[j + 1]\n",
    "            \n",
    "        #     ret.append(dp[0])\n",
    "        \n",
    "        # dot = -1\n",
    "        # for j in range(n - 1, -1, -1):\n",
    "        #     if ret[j]:\n",
    "        #         dot = j\n",
    "        #         break\n",
    "        \n",
    "        # return s[n - 1:dot:-1] + s\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        # n = len(s)\n",
    "        # dp = [[False] * (n + 1) for _ in range(2)]\n",
    "\n",
    "        # for step in range(n):\n",
    "        #     for i in range(n - step):\n",
    "        #         if step == 0:\n",
    "        #             dp[i][i] = True\n",
    "        #         else:\n",
    "        #             if step == 1:\n",
    "        #                 dp[i][i + step] = s[i] == s[i + 1]\n",
    "        #             else:\n",
    "        #                 dp[i][i + step] = (s[i] == s[i + step]) and dp[i + 1][i + step - 1]\n",
    "        \n",
    "        # dot = -1\n",
    "        # for j in range(n - 1, -1, -1):\n",
    "        #     if dp[0][j]:\n",
    "        #         dot = j\n",
    "        #         break\n",
    "        \n",
    "        # return s[n - 1:dot:-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        fail = [0]*n\n",
    "        for i in range(1,n):\n",
    "            j = fail[i-1]\n",
    "            while j>0 and s[i]!=s[j]:\n",
    "                j = fail[j-1]\n",
    "            if s[i]==s[j]:\n",
    "                fail[i] = j+1\n",
    "        s1 = \"\".join(reversed(s))\n",
    "        # 进行匹配\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while j>0 and s1[i]!=s[j]:\n",
    "                j = fail[j-1]\n",
    "            if s1[i]==s[j]:\n",
    "                j+=1\n",
    "        # 需要拿到j的位置\n",
    "        add = s[j:]\n",
    "        return add[::-1]+s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        \"\"\"\n",
    "        manacher 马拉车\n",
    "        \"\"\"\n",
    "        # 预处理\n",
    "        s2 = '?' + s.replace('', '#') + '!'\n",
    "        n = len(s2)\n",
    "        f = [0] * n\n",
    "\n",
    "        right = 0\n",
    "        center = 0\n",
    "        ans_center = 0\n",
    "\n",
    "        for i in range(1, n-1):\n",
    "            mirror = (2 * center) - i\n",
    "            f[i] = 1 if i > right else min(f[mirror], right - i)\n",
    "\n",
    "            while s2[i - f[i]] == s2[i + f[i]]:\n",
    "                f[i] += 1\n",
    "\n",
    "            if f[i] + i > right:\n",
    "                right = f[i] + i\n",
    "                center = i\n",
    "            # 记录下，半径能到达字符串最左端的回文串中心\n",
    "            if f[i] > ans_center and i - f[i] == 0:\n",
    "                ans_center = i\n",
    "\n",
    "        ans = ''\n",
    "        for i in range(n-3, 2*ans_center-1, -2):\n",
    "            ans += s2[i]\n",
    "\n",
    "        return ans + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, string: str) -> str:\n",
    "        s = \"#\".join(\"^{}$\".format(string))\n",
    "        size = len(s)\n",
    "        p = [0] * size\n",
    "        c, r = 0, 0\n",
    "        for i in range(1, size - 1):\n",
    "            if i < r:\n",
    "                p[i] = max(0, min(p[2 * c - i], r - i))\n",
    "            while s[i + p[i] + 1] == s[i - p[i] - 1]:\n",
    "                p[i] += 1\n",
    "            if i + p[i] > r:\n",
    "                c, r = i, i + p[i]\n",
    "        startindex = -1\n",
    "        for i in range(1, size):\n",
    "            if i - p[i] == 1:\n",
    "                startindex = i\n",
    "        return string[(startindex + p[startindex]) // 2:][::-1] + \\\n",
    "            string[(startindex - p[startindex]) // 2 : ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        def getManacherStr(s):\n",
    "            res = ''\n",
    "            for i in s:\n",
    "                res += '#' + i\n",
    "\n",
    "            return res + '#'\n",
    "\n",
    "        ms = getManacherStr(s)\n",
    "        len_ms = len(ms)\n",
    "        pArr = [0 for _ in range(len_ms)]\n",
    "        center = -1\n",
    "        r_border = -1\n",
    "\n",
    "        need = 0\n",
    "\n",
    "        for i in range(len_ms):\n",
    "            pArr[i] = min(pArr[2 * center - i], r_border - i) if r_border > i else 1\n",
    "\n",
    "            while i + pArr[i] < len_ms and i - pArr[i] > -1:\n",
    "                if ms[i + pArr[i]] == ms[i - pArr[i]]:\n",
    "                    pArr[i] += 1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            if i + pArr[i] > r_border:\n",
    "                r_border = i + pArr[i]\n",
    "                center = i\n",
    "\n",
    "            if i - pArr[i] + 1 <= 1:\n",
    "                need = i\n",
    "\n",
    "        need_s = ms[need + pArr[need]:][::-1]\n",
    "        need_s = need_s.replace('#', '')\n",
    "        return need_s + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        S = '#'\n",
    "        for c in s: S = S + c + '#'\n",
    "        N = len(S)\n",
    "        C = R = 0\n",
    "        p = [0]*N\n",
    "        for i in range(1,N):\n",
    "            j = min(p[2*C-i],R-i) if i<R else 0\n",
    "            while i-j-1 >= 0 and i+j+1 < N and S[i-j-1] == S[i+j+1]: j += 1\n",
    "            p[i] = j\n",
    "            if i+j > R: C,R = i,i+j\n",
    "        for k in range(N-1,-1,-1):\n",
    "            if p[k] == k: break\n",
    "        #print(S,p)\n",
    "        return s[k:][::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getManacherString(self, str):\n",
    "        res = ''\n",
    "        for i in str:\n",
    "            res += '#' + i\n",
    "        return res + '#'\n",
    "\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        mStr = self.getManacherString(s)\n",
    "        lens = len(mStr)\n",
    "\n",
    "        pArr = [1 for _ in range(lens)]\n",
    "        pR = index = -1\n",
    "\n",
    "        r = -1\n",
    "\n",
    "        for i in range(lens):\n",
    "            pArr[i] = min(pArr[2 * index - i], pR - i) if pR > i else 1\n",
    "\n",
    "            while i + pArr[i] < lens and i - pArr[i] > -1:\n",
    "                if mStr[i + pArr[i]] == mStr[i - pArr[i]]:\n",
    "                    pArr[i] += 1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            if i + pArr[i] > pR:\n",
    "                pR = i + pArr[i]\n",
    "                index = i\n",
    "\n",
    "            if i - pArr[i] + 1 <= 1:\n",
    "                r = i\n",
    "\n",
    "        if pArr[r] - 1 == len(s):\n",
    "            return s\n",
    "        return s[-(len(s) - (pArr[r] - 1)):][::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        s=\"#\"+\"#\".join(s[::-1])+\"#\"\n",
    "        n=len(s)\n",
    "        dp=[0]*n\n",
    "        index,r,maxi,maxlen=-1,-1,0,0\n",
    "        for i in range(n):\n",
    "            dp[i]=min(r-i,dp[2*index-i]) if r>i else 1\n",
    "            while i-dp[i]>=0 and i+dp[i]<n and s[i-dp[i]]==s[i+dp[i]]:\n",
    "                dp[i]+=1\n",
    "            if i+dp[i]>r:\n",
    "                r=i+dp[i]\n",
    "                index=i\n",
    "            if r==n:\n",
    "                maxi=index\n",
    "                maxlen=dp[index]\n",
    "                break\n",
    "        tmp=s[:maxi-maxlen+1]\n",
    "        res=s+tmp[::-1]\n",
    "        return res.replace(\"#\",\"\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        def prefix_function(s):\n",
    "            n = len(s)\n",
    "            pi = [''] * n\n",
    "            j = -1\n",
    "            pi[0] = j\n",
    "            for i in range(1, n):\n",
    "                while j >= 0 and s[i] != s[j+1]:  # 当前位置s[i]与s[j]不等\n",
    "                    j = pi[j]  # j指向之前位置，s[i]与s[j]继续比较\n",
    "                if s[i] == s[j+1]:  # s[i]与s[j]相等，j+1，指向后一位\n",
    "                    j += 1\n",
    "                pi[i] = j\n",
    "            print(pi)\n",
    "            return pi\n",
    "\n",
    "        pi = prefix_function(s + '#' + s[::-1])  # s+'#'+s[::-1]的前缀函数\n",
    "        if pi[-1] == len(s):  # 前缀函数的最后一位即为s的最长回文前缀的长度\n",
    "            return s\n",
    "        else:\n",
    "            return s[pi[-1]+1:][::-1] + s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return \"\"\n",
    "        rev_s = s[::-1]\n",
    "        s_new = s + '#' + rev_s\n",
    "        kmp = [0] * (2 * n + 1)\n",
    "        j = 0\n",
    "        for i in range(1, 2 * n + 1):\n",
    "            while j > 0 and s_new[j] != s_new[i]:\n",
    "                j = kmp[j - 1]\n",
    "            if s_new[j] == s_new[i]:\n",
    "                j += 1\n",
    "            kmp[i] = j\n",
    "        return rev_s[:n - kmp[2 * n]] + s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        def manacher():\n",
    "            #马拉车算法\n",
    "            arm = [0] * n\n",
    "            l,r = 0,-1\n",
    "            for i in range(0,n):\n",
    "                k = 1 if i > r else min(arm[l+r-i],r-i+1)\n",
    "\n",
    "                # 持续增加回文串的长度\n",
    "                while 0 <= i-k and i + k < n and s[i-k] == s[i + k]:\n",
    "                    k += 1\n",
    "                arm[i] = k\n",
    "                # 更新右侧最远的回文串边界\n",
    "                k -= 1\n",
    "                if i+k > r:\n",
    "                    l = i - k\n",
    "                    r = i + k\n",
    "            # 返回每个位置往右的臂长\n",
    "            return arm\n",
    "        s = \"#\" + \"#\".join(list(s)) + \"#\"\n",
    "        n = len(s)\n",
    "        dp = manacher()\n",
    "        right = 0\n",
    "        for i in range(n):\n",
    "            if i - dp[i] + 1 == 0 and i + dp[i] > right:\n",
    "                right = i + dp[i]\n",
    "        m = len(s[:right].replace('#',''))\n",
    "        s = s.replace('#','')\n",
    "        return s[m:][::-1] + s[:m] + s[m:]    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def shortestPalindrome(self, s: str) -> str:\r\n",
    "\r\n",
    "        if s[::-1] == s:\r\n",
    "            return s\r\n",
    "        # O(n) 寻找最长的前缀回文串\r\n",
    "        mx_pre = 0\r\n",
    "        ss = []\r\n",
    "        for x in s :\r\n",
    "            ss.append('#')\r\n",
    "            ss.append(x)\r\n",
    "        ss.append('#')\r\n",
    "        ss = \"\".join(ss)\r\n",
    "        n = len(ss)\r\n",
    "        # manacher 算法\r\n",
    "        mx = 0\r\n",
    "        d1 = [0] * n\r\n",
    "        l, r = 0, -1\r\n",
    "        for i in range(0, n):\r\n",
    "            k = 1 if i > r else min(d1[l + r - i], r - i + 1)\r\n",
    "            while 0 <= i - k and i + k < n and ss[i - k] == ss[i + k]:\r\n",
    "                k += 1\r\n",
    "            d1[i] = k\r\n",
    "            if d1[i] > i :\r\n",
    "                #找到了一个前缀回文\r\n",
    "                if ss[i] == '#':\r\n",
    "                    mx_pre = d1[i] // 2 * 2\r\n",
    "                else:\r\n",
    "                    mx_pre = d1[i] - 1\r\n",
    "            k -= 1\r\n",
    "            if i + k > r:\r\n",
    "                l = i - k\r\n",
    "                r = i + k\r\n",
    "                \r\n",
    "        return s[mx_pre - len(s):][::-1] + s\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Manacher:\n",
    "    \"\"\"马拉车算法 O(n)\"\"\"\n",
    "\n",
    "    def __init__(self, s: str):\n",
    "        self._s = s\n",
    "        self._n = len(s)\n",
    "        self.oddRadius = self._getOddRadius()\n",
    "        \"\"\"\n",
    "        - 每个中心点的奇回文半径 `radius`\n",
    "        - 最长回文切片为`[pos-radius+1:pos+radius]`\n",
    "        - 以此为中心的回文个数为`radius`\n",
    "        \"\"\"\n",
    "        self.evenRadius = self._getEvenRadius()\n",
    "        \"\"\"\n",
    "        - 每个中心点的偶回文半径 `radius`\n",
    "        - 最长回文切片为`[pos-radius:pos+radius]`\n",
    "        - 以此为中心的回文个数为`radius`\n",
    "        \"\"\"\n",
    "        self._maxOdd1: Optional[List[int]] = None\n",
    "        self._maxOdd2: Optional[List[int]] = None\n",
    "        self._maxEven1: Optional[List[int]] = None\n",
    "        self._maxEven2: Optional[List[int]] = None\n",
    "\n",
    "    def isPalindrome(self, left: int, right: int) -> bool:\n",
    "        \"\"\"查询切片s[left:right]是否为回文串\n",
    "        空串不为回文串\n",
    "        \"\"\"\n",
    "        if not 0 <= left < right <= self._n:\n",
    "            return False\n",
    "\n",
    "        len_ = right - left\n",
    "        mid = (left + right) // 2\n",
    "        if len_ % 2 == 1:\n",
    "            return self.oddRadius[mid] >= len_ // 2 + 1\n",
    "        return self.evenRadius[mid] >= len_ // 2\n",
    "\n",
    "    def getLongestOddStartsAt(self, index: int) -> int:\n",
    "        \"\"\"以s[index]开头的最长奇回文子串的长度\"\"\"\n",
    "        if self._maxOdd1 is None:\n",
    "            self._maxOdd1 = [1] * self._n\n",
    "            self._maxOdd2 = [1] * self._n\n",
    "            for i, radius in enumerate(self.oddRadius):\n",
    "                start, end = i - radius + 1, i + radius - 1\n",
    "                length = 2 * radius - 1\n",
    "                self._maxOdd1[start] = max(self._maxOdd1[start], length)\n",
    "                self._maxOdd2[end] = max(self._maxOdd2[end], length)\n",
    "\n",
    "            # 根据左右更新端点\n",
    "            for i in range(self._n):\n",
    "                if i - 1 >= 0:\n",
    "                    self._maxOdd1[i] = max(self._maxOdd1[i], self._maxOdd1[i - 1] - 2)\n",
    "                if i + 1 < self._n:\n",
    "                    self._maxOdd2[i] = max(self._maxOdd2[i], self._maxOdd2[i + 1] - 2)\n",
    "        return self._maxOdd1[index]\n",
    "\n",
    "    def getLongestOddEndsAt(self, index: int) -> int:\n",
    "        \"\"\"以s[index]结尾的最长奇回文子串的长度\"\"\"\n",
    "        if self._maxOdd2 is None:\n",
    "            self._maxOdd1 = [1] * self._n\n",
    "            self._maxOdd2 = [1] * self._n\n",
    "            for i, radius in enumerate(self.oddRadius):\n",
    "                start, end = i - radius + 1, i + radius - 1\n",
    "                length = 2 * radius - 1\n",
    "                self._maxOdd1[start] = max(self._maxOdd1[start], length)\n",
    "                self._maxOdd2[end] = max(self._maxOdd2[end], length)\n",
    "\n",
    "            # 根据左右更新端点\n",
    "            for i in range(self._n):\n",
    "                if i - 1 >= 0:\n",
    "                    self._maxOdd1[i] = max(self._maxOdd1[i], self._maxOdd1[i - 1] - 2)\n",
    "                if i + 1 < self._n:\n",
    "                    self._maxOdd2[i] = max(self._maxOdd2[i], self._maxOdd2[i + 1] - 2)\n",
    "        return self._maxOdd2[index]\n",
    "\n",
    "    def getLongestEvenStartsAt(self, index: int) -> int:\n",
    "        \"\"\"以s[index]开头的最长偶回文子串的长度\"\"\"\n",
    "        if self._maxEven1 is None:\n",
    "            self._maxEven1 = [0] * self._n\n",
    "            self._maxEven2 = [0] * self._n\n",
    "            for i, radius in enumerate(self.evenRadius):\n",
    "                if radius == 0:\n",
    "                    continue\n",
    "                start = i - radius\n",
    "                end = start + 2 * radius - 1\n",
    "                length = 2 * radius\n",
    "                self._maxEven1[start] = max(self._maxEven1[start], length)\n",
    "                self._maxEven2[end] = max(self._maxEven2[end], length)\n",
    "\n",
    "            # 根据左右更新端点\n",
    "            for i in range(self._n):\n",
    "                if i - 1 >= 0:\n",
    "                    self._maxEven1[i] = max(self._maxEven1[i], self._maxEven1[i - 1] - 2)\n",
    "                if i + 1 < self._n:\n",
    "                    self._maxEven2[i] = max(self._maxEven2[i], self._maxEven2[i + 1] - 2)\n",
    "        return self._maxEven1[index]\n",
    "\n",
    "    def getLongestEvenEndsAt(self, index: int) -> int:\n",
    "        \"\"\"以s[index]结尾的最长偶回文子串的长度\"\"\"\n",
    "        if self._maxEven2 is None:\n",
    "            self._maxEven1 = [0] * self._n\n",
    "            self._maxEven2 = [0] * self._n\n",
    "            for i, radius in enumerate(self.evenRadius):\n",
    "                if radius == 0:\n",
    "                    continue\n",
    "                start = i - radius\n",
    "                end = start + 2 * radius - 1\n",
    "                length = 2 * radius\n",
    "                self._maxEven1[start] = max(self._maxEven1[start], length)\n",
    "                self._maxEven2[end] = max(self._maxEven2[end], length)\n",
    "\n",
    "            # 根据左右更新端点\n",
    "            for i in range(self._n):\n",
    "                if i - 1 >= 0:\n",
    "                    self._maxEven1[i] = max(self._maxEven1[i], self._maxEven1[i - 1] - 2)\n",
    "                if i + 1 < self._n:\n",
    "                    self._maxEven2[i] = max(self._maxEven2[i], self._maxEven2[i + 1] - 2)\n",
    "        return self._maxEven2[index]\n",
    "\n",
    "    def _getOddRadius(self) -> List[int]:\n",
    "        \"\"\"获取每个中心点的奇回文半径`radius`\n",
    "        回文为`[pos-radius+1:pos+radius]`\n",
    "        \"\"\"\n",
    "        res = [0] * self._n\n",
    "        left, right = 0, -1\n",
    "        for i in range(self._n):\n",
    "            k = 1 if i > right else min(res[left + right - i], right - i + 1)\n",
    "            while 0 <= i - k and i + k < self._n and self._s[i - k] == self._s[i + k]:\n",
    "                k += 1\n",
    "            res[i] = k\n",
    "            k -= 1\n",
    "            if i + k > right:\n",
    "                left = i - k\n",
    "                right = i + k\n",
    "        return res\n",
    "\n",
    "    def _getEvenRadius(self) -> List[int]:\n",
    "        \"\"\"获取每个中心点的偶回文半径`radius`\n",
    "        回文为`[pos-radius:pos+radius]`\n",
    "        \"\"\"\n",
    "        res = [0] * self._n\n",
    "        left, right = 0, -1\n",
    "        for i in range(self._n):\n",
    "            k = 0 if i > right else min(res[left + right - i + 1], right - i + 1)\n",
    "            while 0 <= i - k - 1 and i + k < self._n and self._s[i - k - 1] == self._s[i + k]:\n",
    "                k += 1\n",
    "            res[i] = k\n",
    "            k -= 1\n",
    "            if i + k > right:\n",
    "                left = i - k - 1\n",
    "                right = i + k\n",
    "        return res\n",
    "\n",
    "    def __len__(self) -> int:\n",
    "        return self._n\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        if s==s[::-1]:\n",
    "            return s\n",
    "        ma=Manacher(s)\n",
    "        maxlen=1\n",
    "        n=len(s)\n",
    "        for i in range(1,n):\n",
    "            if ma.isPalindrome(0,i+1):\n",
    "                #print(i)\n",
    "                maxlen=i-0+1\n",
    "        p=s[-(n-maxlen):]\n",
    "        #print(p,n-maxlen)\n",
    "        return p[::-1]+s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        def manacher():\n",
    "            #马拉车算法\n",
    "            arm = [0] * n\n",
    "            l,r = 0,-1\n",
    "            for i in range(0,n):\n",
    "                k = 1 if i > r else min(arm[l+r-i],r-i+1)\n",
    "\n",
    "                # 持续增加回文串的长度\n",
    "                while 0 <= i-k and i + k < n and s[i-k] == s[i + k]:\n",
    "                    k += 1\n",
    "                arm[i] = k\n",
    "                # 更新右侧最远的回文串边界\n",
    "                k -= 1\n",
    "                if i+k > r:\n",
    "                    l = i - k\n",
    "                    r = i + k\n",
    "            # 返回每个位置往右的臂长\n",
    "            return arm\n",
    "        s = \"#\" + \"#\".join(list(s)) + \"#\"\n",
    "        n = len(s)\n",
    "        dp = manacher()\n",
    "        right = 0\n",
    "        for i in range(n):\n",
    "            if i - dp[i] + 1 == 0 and i + dp[i] > right:\n",
    "                right = i + dp[i]\n",
    "        m = len(s[:right].replace('#',''))\n",
    "        s = s.replace('#','')\n",
    "        return s[m:][::-1] + s[:m] + s[m:]    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        t = list(s)\n",
    "        t.reverse()\n",
    "        t = ''.join(t)\n",
    "        s_t = ' ' + s + '#' + t\n",
    "        ## KMP\n",
    "        ne = [0] * (2 * n + 2)\n",
    "        j = 0\n",
    "        i = 2\n",
    "        while i <= n * 2 + 1:\n",
    "            while j and s_t[i] != s_t[j + 1]:\n",
    "                j = ne[j]\n",
    "            if s_t[i] == s_t[j + 1]: j += 1\n",
    "            ne[i] = j\n",
    "            i += 1\n",
    "        print(s_t)\n",
    "        print(ne)\n",
    "\n",
    "        l = ne[2 * n + 1]\n",
    "        tail = s[l:]\n",
    "        print(tail)\n",
    "        tail = list(tail)\n",
    "        tail.reverse()\n",
    "        tail = ''.join(tail)\n",
    "        res = tail + s\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        oriS = s\n",
    "        s = ['#' + c for c in s] + ['#']\n",
    "        n = len(s)\n",
    "        LPS = [0] * n\n",
    "        res = L = C = R = 0\n",
    "        for i in range(len(s)):\n",
    "            if i < R:\n",
    "                LPS[i] = min(R - i, LPS[C - (i - C)])\n",
    "            while LPS[i] + 1 < n and i - LPS[i] - 1 >= 0 and s[LPS[i] + 1] == s[i - LPS[i] - 1]:\n",
    "                LPS[i] += 1\n",
    "            if i + LPS[i] > R:\n",
    "                C, R = i, LPS[i] + i\n",
    "        res = 1\n",
    "        for i in range(n):\n",
    "            if LPS[i] == i:\n",
    "                res = i + 1\n",
    "        return oriS[res:][::-1] + oriS\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        def prefix_function(s):\n",
    "            n = len(s)\n",
    "            pre = [0 for i in range(n)]\n",
    "            j = 0\n",
    "            for i in range(1, n):\n",
    "                while j>0 and s[i]!=s[j]:\n",
    "                    j = pre[j-1]\n",
    "                if s[i] == s[j]:\n",
    "                    j = j + 1\n",
    "                pre[i] = j\n",
    "            return pre\n",
    "        pre = prefix_function(s + '#' + s[::-1])\n",
    "        if pre[-1] == len(s):\n",
    "            return s\n",
    "        else:\n",
    "            return s[pre[-1]:][::-1] + s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def manacher(self, s):\n",
    "        radius = [0] * len(s)\n",
    "        best_mid, best_right = 0, 0\n",
    "        for i in range(1, len(s)-1):\n",
    "            mirror_left = 2*best_mid - i\n",
    "            if i < best_right:\n",
    "                radius[i] = min(\n",
    "                    radius[mirror_left],\n",
    "                    best_right-i\n",
    "                )\n",
    "            else:\n",
    "                radius[i] = 0\n",
    "            \n",
    "            while s[i+radius[i]+1] == s[i-radius[i]-1]:\n",
    "                radius[i] += 1\n",
    "            \n",
    "            if i+radius[i] > best_right:\n",
    "                best_mid = i\n",
    "                best_right = i+radius[i]\n",
    "        return radius\n",
    "            \n",
    "\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        if len(s) <= 1:\n",
    "            return s\n",
    "        s = \"$\" + \"#\".join(list(s)) + \"&\"\n",
    "        n = len(s)\n",
    "        dp = self.manacher(s)\n",
    "        right = 0\n",
    "        for i in range(n):\n",
    "            if i - dp[i] == 1 and i + dp[i] > right:\n",
    "                right = i + dp[i]\n",
    "        # print(dp)\n",
    "        # print(right)\n",
    "        m = len(s[:right+1].replace('#', '').replace(\"&\", \"\").replace(\"$\", \"\"))\n",
    "        # print(m)\n",
    "        s = s.replace('#', '').replace(\"&\", \"\").replace(\"$\", \"\")\n",
    "        return s[m:][::-1] + s[:m] + s[m:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str: \n",
    "        n = len(s) \n",
    "        new_s = s + \"#\" + s[len(s)-1::-1] \n",
    "        prefix = [0 for _ in range(len(new_s))]\n",
    "        for i in range(1, len(new_s)):\n",
    "            if new_s[prefix[i-1]] == new_s[i]:\n",
    "                prefix[i] = prefix[i-1] + 1\n",
    "            else:\n",
    "                j = prefix[i-1] - 1\n",
    "                while j >= 0 and new_s[prefix[j]] != new_s[i]:\n",
    "                    j = prefix[j] - 1 \n",
    "                if j >= 0:\n",
    "                    prefix[i] = prefix[j] + 1 \n",
    "                else:\n",
    "                    prefix[i] = 0  \n",
    "        return s[len(s)-1:prefix[-1]-1:-1] + s    \n",
    "                \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        # 参考题解 KMP算法\n",
    "        def prefix_function(s):\n",
    "            # 前缀函数（next数组）来记录模式串的局部匹配信息\n",
    "            # 这里s是有正序s和反序s拼接而成的\n",
    "            n = len(s)\n",
    "            pi = [0] * n\n",
    "\n",
    "            j = 0\n",
    "            for i in range(1, n):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = pi[j-1]\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                pi[i] = j\n",
    "            return pi\n",
    "        \n",
    "        pi = prefix_function(s + '#' + s[::-1])\n",
    "        if pi[-1] == len(s):\n",
    "            return s\n",
    "        else:\n",
    "            return s[pi[-1]:][::-1] + s\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shortestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        r_words = []\n",
    "        words = []\n",
    "        location = [-1]*len(s)\n",
    "        for i in range(len(s)):\n",
    "            r_words.append(s[i])\n",
    "            words.append(s[len(s) - 1 - i])\n",
    "        for i in range(1,len(s)):\n",
    "            last = location[i-1]\n",
    "            while last >-1 and s[i]!=s[last+1]:\n",
    "                last = location[last]\n",
    "            if s[i] == s[last+1]:\n",
    "                location[i] = last + 1\n",
    "        print(location)\n",
    "        p1 = -1\n",
    "        p2 = -1\n",
    "        for i in range(len(s)):\n",
    "            p1 +=1\n",
    "            p2 += 1\n",
    "            while r_words[p1]!=words[p2]:\n",
    "                p1 = location[p1 - 1] + 1\n",
    "                if p1 == 0 and r_words[p1]!=words[p2]:\n",
    "                    p1 = -1\n",
    "                    break\n",
    "        result = \"\"\n",
    "        for i in range(len(s)):\n",
    "            result = result + words[i]\n",
    "        for i in range(p1+1,len(s)):\n",
    "            result = result + r_words[i]\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        if len(s)<=1:\n",
    "            return s\n",
    "        mod = 10**9 + 7\n",
    "        nl = [0]*len(s)\n",
    "        l = [0]* len(s)\n",
    "        m = [0]* len(s)\n",
    "        m[0] = 1\n",
    "        k = 1\n",
    "        for i in range(1,len(s)):\n",
    "            m[i] = (m[i-1] * 26) % mod\n",
    "        k = 0\n",
    "        \n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            k = k * 26 + (ord(s[i]) - ord('a') + 1)\n",
    "            k = k %(mod)\n",
    "            nl[i] = k\n",
    "        \n",
    "        k = 0\n",
    "        for i in range(len(s)):\n",
    "            k = k * 26 + (ord(s[i]) - ord('a') + 1)\n",
    "            k = k %(mod)\n",
    "            l[i] = k \n",
    "        maxl = 2*len(s)\n",
    "        ans=s[::-1]+s\n",
    "        \n",
    "        for i in range(-1,len(s)):\n",
    "            mv = 0 if i==-1 else l[i]\n",
    "            if (i + 1) <= len(s) - i -2:\n",
    "                v = 0 if 2*i + 3 >= len(s) else nl[2*i + 3]\n",
    "                p = nl[i + 2]  -  ( v* m[ i + 1] % mod ) \n",
    "                if p <0:\n",
    "                    p+=mod\n",
    "                if p == mv:\n",
    "                    al = 2*(len(s) - i - 2) + 1\n",
    "                    if al < maxl:\n",
    "                        maxl = al\n",
    "                        ans = s[i+2:][::-1] + s[i+1:]\n",
    "            if (i + 1) <= len(s) - i -1:\n",
    "                v = 0 if 2*i + 2>=len(s) else nl[2*i + 2]\n",
    "                p = nl[i + 1]  -  ( v * m[ i + 1] % mod ) \n",
    "                if p <0:\n",
    "                    p+=mod\n",
    "                if p == mv:\n",
    "                    al = 2*(len(s) -i - 1)\n",
    "                    if al < maxl:\n",
    "                        maxl = al\n",
    "                        ans =  s[i+1:][::-1] + s[i+1:]\n",
    "            # rl = len(s) - i \n",
    "            # if  rl <= len(s) - rl - 1:\n",
    "            #     p = l[len(s) - (rl) - 2] - ( l[len(s) - 2*rl - 2] if len(s) - 2*rl - 2>=0 else 0) *m[rl] % mod\n",
    "            #     if p<0:\n",
    "            #         p+=mod\n",
    "            #     if nl[i] == p:\n",
    "            #         al = 2*(i) + 1\n",
    "            #         if al< maxl:\n",
    "            #             maxl = al\n",
    "            #             ans = s[:i+1]  + s[:i][::-1]\n",
    "            # if  rl <= len(s) - rl :\n",
    "            #     v = 0 if len(s) - 2*rl - 1<0 else l[len(s) - 2*rl - 1]\n",
    "            #     p = l[len(s) - (rl) - 1] - v*m[rl] % mod\n",
    "            #     if p<0:\n",
    "            #         p+=mod\n",
    "            #     if nl[i] == p:\n",
    "            #         al = 2*(i)\n",
    "            #         if al< maxl:\n",
    "            #             maxl = al\n",
    "            #             ans = s[:i]  + s[:i][::-1]\n",
    "        return ans \n",
    "             \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        def extends(left: int, right: int) -> int:\n",
    "            while left >= 0 and right < len(s) and s[left] == s[right]:\n",
    "                left -= 1\n",
    "                right += 1\n",
    "            return (right - left - 2) // 2\n",
    "\n",
    "        tmp = s\n",
    "        start, end = 0, -1\n",
    "        s = '#' + '#'.join(s) + \"#\"\n",
    "        # 回文半径\n",
    "        P = []\n",
    "        # 右边界\n",
    "        y = -1\n",
    "        # 中心点\n",
    "        c = -1\n",
    "        for i in range(len(s)):\n",
    "            if y >= i:\n",
    "                i_sym = 2 * c - i\n",
    "                min_arm_len = min(P[i_sym], y - i)\n",
    "                cur_arm_len = extends(i - min_arm_len, i + min_arm_len)\n",
    "            else:\n",
    "                cur_arm_len = extends(i, i)\n",
    "            P.append(cur_arm_len)\n",
    "            if i + cur_arm_len > y:\n",
    "                c = i\n",
    "                y = c + cur_arm_len\n",
    "            if 2 * cur_arm_len + 1 > end - start:\n",
    "                start = i - cur_arm_len\n",
    "                end = i + cur_arm_len\n",
    "        k = 0\n",
    "        for i in range(len(s)):\n",
    "            if P[i] == i:\n",
    "                k = i\n",
    "        return s[k * 2+1::2][::-1] + tmp\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        ss = '?#' + '#'.join(list(s)) + '#@'\n",
    "        n = len(ss)\n",
    "        p = [0] * n\n",
    "        id, mx = 0, -1\n",
    "        ans = 0\n",
    "        for i in range(1, n - 1):\n",
    "            p[i] = 1 if i > mx else min(mx - i, p[2 * id - i])\n",
    "            while ss[i - p[i]] == ss[i + p[i]]:\n",
    "                p[i] += 1\n",
    "            if i + p[i] > mx:\n",
    "                id, mx = i, i + p[i]\n",
    "            if i - p[i] == 0:\n",
    "                ans = max(ans, p[i] - 1)\n",
    "        return s[-1: ans - len(s) - 1 : -1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        ss = s+'#'+s[::-1]\n",
    "        lps = [0]*len(ss)\n",
    "        i = 0\n",
    "        for j in range(1, len(ss)):\n",
    "            while i>0 and ss[i] != ss[j]:\n",
    "                i = lps[i-1]\n",
    "\n",
    "            if ss[i] == ss[j]:\n",
    "                i += 1\n",
    "\n",
    "            lps[j] = i\n",
    "\n",
    "        return s[-1:lps[-1]-1:-1]+s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        ss = s+'#'+s[::-1]\n",
    "        lps = [0]*len(ss)\n",
    "        i = 0\n",
    "        for j in range(1, len(ss)):\n",
    "            while i>0 and ss[i] != ss[j]:\n",
    "                i = lps[i-1]\n",
    "\n",
    "            if ss[i] == ss[j]:\n",
    "                i += 1\n",
    "\n",
    "            lps[j] = i\n",
    "\n",
    "        return s[-1:lps[-1]-1:-1]+s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        def getNxt(s):\n",
    "            nxt = [0]\n",
    "            i, j = 1, 0\n",
    "            while i < len(s):\n",
    "                if s[i] == s[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                    nxt.append(j)\n",
    "                elif j:\n",
    "                    j = nxt[j - 1]\n",
    "                else:\n",
    "                    nxt.append(0)\n",
    "                    i += 1\n",
    "            return nxt\n",
    "\n",
    "        nxt = getNxt(s + '#' + s[::-1])\n",
    "        return s[::-1][:len(s) - nxt[-1]] + s\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def pref(s):\n",
    "    n = len(s)\n",
    "    pi = [0] * n\n",
    "    for i in range(1, n):\n",
    "        j = pi[i - 1]\n",
    "        while j > 0 and s[i] != s[j]:\n",
    "            j = pi[j - 1]\n",
    "        if s[i] == s[j]:\n",
    "            j += 1\n",
    "        pi[i] = j\n",
    "    return pi\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        if len(s)==0:\n",
    "            return ''\n",
    "        # if len(s)==1:\n",
    "        #     return 0\n",
    "        s1 = s[::-1]\n",
    "        if s1==s:\n",
    "            # print(s, 111, s1)\n",
    "            return s\n",
    "        s2 = s + \"#\" + s1 \n",
    "        tmp = pref(s2) \n",
    "        # print(tmp)\n",
    "        l = tmp[-1]\n",
    "        pre = s[l:][::-1] \n",
    "        return pre +s\n",
    "        # return len(s) - tmp[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        s_rev = s[::-1]\n",
    "        new_s = s + \"#\" + s_rev\n",
    "        n = len(new_s)\n",
    "        next_arr = [0] * n\n",
    "        \n",
    "        j = 0\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and new_s[i] != new_s[j]:\n",
    "                j = next_arr[j - 1]\n",
    "            if new_s[i] == new_s[j]:\n",
    "                j += 1\n",
    "            next_arr[i] = j\n",
    "        \n",
    "        palindrome_length = next_arr[-1]\n",
    "        shortest_palindrome = s_rev[:len(s) - palindrome_length] + s\n",
    "        \n",
    "        return shortest_palindrome\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        ss = s+'#'+s[::-1]\n",
    "        n = len(ss)\n",
    "        lps = [0]*n\n",
    "\n",
    "        i = 0\n",
    "        for j in range(1, n):\n",
    "            while i>0 and ss[i] != ss[j]:\n",
    "                i = lps[i-1]\n",
    "\n",
    "            if ss[i] == ss[j]:\n",
    "                i += 1\n",
    "\n",
    "            lps[j] = i\n",
    "\n",
    "        return s[-1:lps[-1]-1:-1]+s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "\n",
    "        \n",
    "        \n",
    "        '''KMP模板'''\n",
    "        def prefix_function(s):     \n",
    "            n = len(s)\n",
    "            pi = [0] * n\n",
    "            j, i = 0, 1\n",
    "            while i < n:\n",
    "                if s[i] == s[j]:\n",
    "                    pi[i] = j + 1\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                elif j == 0:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    j = pi[j-1]\n",
    "\n",
    "            return pi\n",
    "        \n",
    "\n",
    "        '''主程序'''\n",
    "        pi = prefix_function(s+'#'+s[::-1])     # s+'#'+s[n-1,...,0]的前缀函数\n",
    "        if pi[-1] == len(s):                    # 前缀函数的最后一位即为s的最长回文前缀的长度\n",
    "            return s\n",
    "        else:\n",
    "            return s[pi[-1]:][::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        \n",
    "        '''KMP模板'''\n",
    "        def prefix_function(s):     \n",
    "            n = len(s)\n",
    "            pi = [0] * n\n",
    "            j, i = 0, 1\n",
    "            while i < n:\n",
    "                if s[i] == s[j]:\n",
    "                    pi[i] = j + 1\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                elif j == 0:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    j = pi[j-1]\n",
    "\n",
    "            return pi\n",
    "        \n",
    "\n",
    "        '''主程序'''\n",
    "        pi = prefix_function(s+'#'+s[::-1])     # s+'#'+s[n-1,...,0]的前缀函数\n",
    "        if pi[-1] == len(s):                    # 前缀函数的最后一位即为s的最长回文前缀的长度\n",
    "            return s\n",
    "        else:\n",
    "            return s[pi[-1]:][::-1] + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        def compute_lps(pattern):\n",
    "            m = len(pattern)\n",
    "            lps = [0] * m\n",
    "            j = 0  # 前一个最长前缀后缀的长度\n",
    "\n",
    "            for i in range(1, m):\n",
    "                while j > 0 and pattern[i] != pattern[j]:\n",
    "                    j = lps[j-1]\n",
    "\n",
    "                if pattern[i] == pattern[j]:\n",
    "                    j += 1\n",
    "\n",
    "                lps[i] = j\n",
    "\n",
    "            return lps\n",
    "\n",
    "        s_rev = s[::-1]\n",
    "        combined = s + \"#\" + s_rev\n",
    "        lps = compute_lps(combined)\n",
    "\n",
    "        # s_rev 中与 s 的最长前缀的长度\n",
    "        common_len = lps[-1]\n",
    "\n",
    "        # 将 s_rev 剩余的部分添加到 s 的前面\n",
    "        return s_rev[:len(s) - common_len] + s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        def build(s):\n",
    "            nxt = [0, 0]\n",
    "            j = 0\n",
    "            for i in range(1, len(s)):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = nxt[j]\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1 \n",
    "                nxt.append(j) \n",
    "            return nxt \n",
    "        \n",
    "        def match(s, p):\n",
    "            nxt = build(p)\n",
    "            # print(nxt)\n",
    "            j = 0\n",
    "            for i in range(len(s)):\n",
    "                while j > 0 and p[j] != s[i]:\n",
    "                    j = nxt[j]\n",
    "                if p[j] == s[i]:\n",
    "                    j += 1 \n",
    "                if j == len(p):\n",
    "                    return i - len(p) + 1\n",
    "                    j = nxt[j]\n",
    "            return - 1\n",
    "        print(match('achkjsdf', 'hkj'))\n",
    "        nxt = build(s + '@' + s[::-1])\n",
    "        maxLen = nxt[-1]\n",
    "        return s[maxLen : ][::-1] + s"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
